package q1092

func shortestCommonSupersequence(str1 string, str2 string) string {
	return get(str1, str2)
}

func getQuestion(str1 string, str2 string) string {
	l1 := len(str1)
	l2 := len(str2)
	if l1 < 1 || l2 < 1 {
		return str1 + str2
	}
	f1 := str1[:1]
	f2 := str2[:1]
	var s1, s2, s3 string

	s1 = f1 + get(str1[1:], str2)
	if len(s1) > l1+1 || len(s1) > l2 {
		s2 = f2 + get(str1, str2[1:])
	} else {
		s2 = s1
	}

	if len(s2) <= len(s1) {
		s1, s2 = s2, s1
	}

	if f1 != f2 {
		s3 = str1 + str2
	} else {
		if len(s1) <= l1 && len(s1) <= l2 {
			return s1
		}
		s3 = f2 + get(str1[1:], str2[1:])
	}
	if len(s3) <= len(s1) {
		return s3
	}
	return s1
}

var m map[string]string = map[string]string{}

func get(str1 string, str2 string) string {
	//return getQuestion(str1,str2)
	var k string
	if str1 <= str2 {
		k = str1 + "," + str2
	} else {
		k = str2 + "," + str1
	}
	if len(m[k]) > 0 {
		//fmt.Println(str1+"+"+str2+"="+m[k]);
		return m[k]
	}
	m[k] = getQuestion(str1, str2)
	return m[k]
}
